#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "subsets.h"

/* Here's a bit of defines */
/* They are used just here, 
   so they do not need to appear in subset.h */

/* The block of the first r 1s */

#define SS_FIRST(r)\
(\
UINT_MAX >> ((sizeof(unsigned int)*8) - r) \
)


/** Indexing */
#define SS_BLOCK_NO(j) ((j)/SS_NOELSINBLOCK)
#define SS_BLOCK_OF(j,s) ((s)->ss_blocks[SS_BLOCK_NO(j)]) 
#define SS_INDEX_IN_BLOCK(j) ((j)%SS_NOELSINBLOCK)

#define SS_BLOCK_SINGLETON(x)\
(\
  1<<(SS_INDEX_IN_BLOCK(x))\
)\

/** Operations **/

char *
ss_name(Subset *s)
{
  return s->name;
}

void
ss_set_name(Subset *s,char *n)
{
  strncpy(s->name,n,SS_NAME_DIM);
}

void
ss_cat_name(Subset *s,char *n)
{
  strncat(s->name,n,SS_NAME_DIM);
}

int
ss_cmp_name(Subset *s,char *n)
{
  return strncmp(s->name,n,SS_NAME_DIM);
}

void 
ss_add_name(Subset *s, char *name, char *sep)
{
  if(ss_cmp_name(s,"") != 0)
      ss_cat_name(s,sep);
  ss_cat_name(s,name);
}

void 
ss_free(Subset * s)
{
  free(s);
}

/* Initialize a subset of n as the empty one (tested) */ 
void
ss_empty(int n,Subset *s)
{
  int i;

  assert(s != NULL);
  assert(n <= SS_MAXEL);
  memset(s,0,sizeof(Subset));

  s->ss_of = n;
  
  for(i = 0; i < SS_NOBLOCKS;i++)
    s->ss_blocks[i] = 0;

  ss_set_name(s,"");
}

/* Initialize a subset of n as the total one (tested) */ 
void
ss_total(int n,Subset *s)
{
  unsigned int i,q,r;

  assert(s != NULL);
  assert(n <= SS_MAXEL);
  memset(s,0,sizeof(Subset));
  
  s->ss_of = n;
  
  q = n/SS_NOELSINBLOCK;
  r = n%SS_NOELSINBLOCK;
  
  for(i=0;i<q;i++)
    s->ss_blocks[i] = 1;

  if(r != 0)
     s->ss_blocks[i++] = SS_FIRST(r);
  
  for(;i<SS_NOBLOCKS;i++)
    s->ss_blocks[i] = 0;

  ss_set_name(s,"");
  
}

/* Initialize a subset of n at random (tested) */ 
void
ss_random(int n,Subset *s)
{
  unsigned int i,q,r;

  assert(s != NULL);
  assert(n <= SS_MAXEL);
  
  s->ss_of = n;
  
  q = n/SS_NOELSINBLOCK;
  r = n%SS_NOELSINBLOCK;
  
  for(i=0;i<q;i++)
    s->ss_blocks[i] = (Block)rand();

  if(r != 0)
     s->ss_blocks[i++] = ((Block)rand()) & SS_FIRST(r);
  
  for(;i<SS_NOBLOCKS;i++)
    s->ss_blocks[i] = 0;

  ss_set_name(s,"random");
 
}

/* Intersection (tested) */ 
void
ss_intersection(Subset *dest,Subset *s1,Subset *s2)
{
  unsigned int i;

  assert(dest != NULL); 
  assert(s1 != NULL);
  assert(s2 != NULL);
  assert(dest->ss_of <= SS_MAXEL);
  assert(dest->ss_of == s1->ss_of);
  assert(dest->ss_of == s2->ss_of);

  for(i=0;i<SS_NOBLOCKS;i++)
    dest->ss_blocks[i] = s1->ss_blocks[i] & s2->ss_blocks[i];

}

/* Union (tested) */ 
void
ss_union(Subset *dest,Subset *s1,Subset *s2)
{
  unsigned int i;

  assert(dest != NULL); 
  assert(s1 != NULL);
  assert(s2 != NULL);
  assert(dest->ss_of <= SS_MAXEL);
  assert(dest->ss_of == s1->ss_of);
  assert(dest->ss_of == s2->ss_of);

  for(i=0;i<SS_NOBLOCKS;i++)
    dest->ss_blocks[i] = s1->ss_blocks[i] | s2->ss_blocks[i];

}

/* Copying (tested) */ 
void
ss_cpy(Subset *dest,Subset *s)
{
  unsigned int i;

  assert(dest != NULL); 
  assert(s != NULL);
  assert(dest->ss_of <= SS_MAXEL);
  assert(dest->ss_of == s->ss_of);
  
  for(i=0;i<SS_NOBLOCKS;i++)
    dest->ss_blocks[i] = s->ss_blocks[i];

}

/* Add element j to subset s (tested) */ 
void
ss_addto(Subset *s,int j)
{
  int q,r;

  assert(s != NULL);
  assert(j <= s->ss_of);
  
  q = j/SS_NOELSINBLOCK;
  r = j%SS_NOELSINBLOCK;
  
  s->ss_blocks[q] |= 1<<r;

}

/* Delete  element j to subset s (tested) */ 
void
ss_delfrom(Subset *s,int j)
{
  int q,r;

  assert(s != NULL);
  assert(j <= s->ss_of);
  
  q = j/SS_NOELSINBLOCK;
  r = j%SS_NOELSINBLOCK;
  
  s->ss_blocks[q] &= ~(1<<r);

}

/* Turn into the complement (tested) */
void
ss_complement(Subset *s)
{
  int i,q,r;

  assert(s != NULL);
  assert(s->ss_of <= SS_MAXEL);
  
   
  q = s->ss_of/SS_NOELSINBLOCK;
  r = s->ss_of%SS_NOELSINBLOCK;
  
  for(i=0;i<q;i++)
    s->ss_blocks[i] = ~s->ss_blocks[i];
  
  if(r > 0)
    s->ss_blocks[i] = (~s->ss_blocks[i]) & SS_FIRST(r);
}

/** Predicates **/
/* Are they equal ? (tested) */ 
int 
ss_equal(Subset *s1,Subset *s2)
{
  int i,q,r;

  assert(s1 != NULL);
  assert(s2 != NULL);
  assert(s1->ss_of == s2->ss_of);

  q = s1->ss_of/SS_NOELSINBLOCK;
  r = s1->ss_of%SS_NOELSINBLOCK;
  
  for(i=0;i<q;i++)
    if( s1->ss_blocks[i] != s2->ss_blocks[i])
     	return 0;
  
  if(r > 0)
    if( (s1->ss_blocks[i] & SS_FIRST(r) ) 
	!= (s2->ss_blocks[i] & SS_FIRST(r)))
      {
	return 0;
      }

  return 1; 
}

/* Is s1 contained in s2 ? (tested) */ 
int 
ss_contained(Subset *s1,Subset *s2)
{
  int i;

  assert(s1 != NULL);
  assert(s2 != NULL);
 
  for(i=0;i<SS_NOBLOCKS;i++)
    if( (s1->ss_blocks[i] | s2->ss_blocks[i]) != s2->ss_blocks[i])
      return 0;

  return 1; 

}

int 
ss_card(Subset * s)
{
  int i=0,x;

  SS_FORALLIN(x,s)
    i++;

  return i;
}

/* Does j belongs to s ? (tested) */ 
int 
ss_belongs(int j,Subset *s)
{
  assert(s != NULL);
 
  return
    (SS_BLOCK_OF(j,s) & SS_BLOCK_SINGLETON(j)) && 1;

}

/** Printing facilities  **/

/* Pretty print to stdout (tested) */

void
ss_print(Subset *s)
{
  int i,q,r;

  assert(s != NULL);

  for(i=0;i<s->ss_of;i++)
    {
      q = i/ SS_NOELSINBLOCK;
      r = i% SS_NOELSINBLOCK;
      printf("%d",s->ss_blocks[q] >> r & 1);
    }
/*   printf("\n"); */
}

/* Morally this does the same as the one before */
void
ss_print_name(Subset *s)
{
  int i;

  if(strncmp(s->name,"",SS_NAME_DIM) == 0)
    for(i=0;i<s->ss_of; i++)
      printf("%d",ss_belongs(i,s));
  else
    printf("%s",ss_name(s));
}

